/*
 *	MP3 quantization
 *
 *	Copyright (c) 1999-2000 Mark Taylor
 *	Copyright (c) 2000-2007 Robert Hegemann
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

/* $Id: VBRQuantize.java,v 1.18 2011/08/27 18:57:12 kenchis Exp $ */

package net.sourceforge.lame.mp3;

import java.util.Arrays;

public class VBRQuantize {

  protected static final int max_range_short[] = {15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 7, 7, 7, 7, 7, 7,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 0, 0};
  protected static final int max_range_long[] = {15, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0};
  protected static final int max_range_long_lsf_pretab[] = {7, 7, 7, 7, 7,
      7, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  QuantizePVT qupvt;
  Takehiro tak;

  public final void setModules(QuantizePVT qupvt, Takehiro tk) {
    this.qupvt = qupvt;
    this.tak = tk;
  }

  private float max_x34(final float[] xr34, int x34Pos, final int bw) {
    float xfsf = 0;
    int j = bw >> 1;
    final int remaining = (j & 0x01);

    for (j >>= 1; j > 0; --j) {
      if (xfsf < xr34[x34Pos + 0]) {
        xfsf = xr34[x34Pos + 0];
      }
      if (xfsf < xr34[x34Pos + 1]) {
        xfsf = xr34[x34Pos + 1];
      }
      if (xfsf < xr34[x34Pos + 2]) {
        xfsf = xr34[x34Pos + 2];
      }
      if (xfsf < xr34[x34Pos + 3]) {
        xfsf = xr34[x34Pos + 3];
      }
      x34Pos += 4;
    }
    if (remaining != 0) {
      if (xfsf < xr34[x34Pos + 0]) {
        xfsf = xr34[x34Pos + 0];
      }
      if (xfsf < xr34[x34Pos + 1]) {
        xfsf = xr34[x34Pos + 1];
      }
    }
    return xfsf;
  }

  private int findLowestScalefac(final float xr34) {
    int sfOk = 255;
    int sf = 128, delsf = 64;
    for (int i = 0; i < 8; ++i) {
      final float xfsf = qupvt.ipow20[sf] * xr34;
      if (xfsf <= QuantizePVT.IXMAX_VAL) {
        sfOk = sf;
        sf -= delsf;
      } else {
        sf += delsf;
      }
      delsf >>= 1;
    }
    return sfOk;
  }

  private int belowNoiseFloor(final float[] xr, int xrPos, float l3xmin,
                              final int bw) {
    float sum = 0.0f;
    for (int i = 0, j = bw; j > 0; ++i, --j) {
      final float x = xr[xrPos + i];
      sum += x * x;
    }
    return (l3xmin - sum) >= -1E-20 ? 1 : 0;
  }

  private void k_34_4(final double x[], final int l3[], final int l3Pos) {
    assert (x[0] <= QuantizePVT.IXMAX_VAL && x[1] <= QuantizePVT.IXMAX_VAL
        && x[2] <= QuantizePVT.IXMAX_VAL && x[3] <= QuantizePVT.IXMAX_VAL);
    l3[l3Pos + 0] = (int) x[0];
    l3[l3Pos + 1] = (int) x[1];
    l3[l3Pos + 2] = (int) x[2];
    l3[l3Pos + 3] = (int) x[3];
    x[0] += qupvt.adj43[l3[l3Pos + 0]];
    x[1] += qupvt.adj43[l3[l3Pos + 1]];
    x[2] += qupvt.adj43[l3[l3Pos + 2]];
    x[3] += qupvt.adj43[l3[l3Pos + 3]];
    l3[l3Pos + 0] = (int) x[0];
    l3[l3Pos + 1] = (int) x[1];
    l3[l3Pos + 2] = (int) x[2];
    l3[l3Pos + 3] = (int) x[3];
  }

  private void k_34_2(final double x[], final int l3[], final int l3Pos) {
    assert (x[0] <= QuantizePVT.IXMAX_VAL && x[1] <= QuantizePVT.IXMAX_VAL);
    l3[l3Pos + 0] = (int) x[0];
    l3[l3Pos + 1] = (int) x[1];
    x[0] += qupvt.adj43[l3[l3Pos + 0]];
    x[1] += qupvt.adj43[l3[l3Pos + 1]];
    l3[l3Pos + 0] = (int) x[0];
    l3[l3Pos + 1] = (int) x[1];
  }

  private float calc_sfb_noise_x34(final float[] xr, final float[] xr34,
                                   int xrPos, int bw, int sf) {
    double x[] = new double[4];
    int l3[] = new int[4];
    final float sfpow = qupvt.pow20[sf + QuantizePVT.Q_MAX2];
    final float sfpow34 = qupvt.ipow20[sf];

    float xfsf = 0;
    int j = bw >> 1;
    final int remaining = (j & 0x01);

    for (j >>= 1; j > 0; --j) {
      x[0] = sfpow34 * xr34[xrPos + 0];
      x[1] = sfpow34 * xr34[xrPos + 1];
      x[2] = sfpow34 * xr34[xrPos + 2];
      x[3] = sfpow34 * xr34[xrPos + 3];

      k_34_4(x, l3, 0);

      x[0] = Math.abs(xr[xrPos + 0]) - sfpow * qupvt.pow43[l3[0]];
      x[1] = Math.abs(xr[xrPos + 1]) - sfpow * qupvt.pow43[l3[1]];
      x[2] = Math.abs(xr[xrPos + 2]) - sfpow * qupvt.pow43[l3[2]];
      x[3] = Math.abs(xr[xrPos + 3]) - sfpow * qupvt.pow43[l3[3]];
      xfsf += (x[0] * x[0] + x[1] * x[1]) + (x[2] * x[2] + x[3] * x[3]);

      xrPos += 4;
    }
    if (remaining != 0) {
      x[0] = sfpow34 * xr34[xrPos + 0];
      x[1] = sfpow34 * xr34[xrPos + 1];

      k_34_2(x, l3, 0);

      x[0] = Math.abs(xr[xrPos + 0]) - sfpow * qupvt.pow43[l3[0]];
      x[1] = Math.abs(xr[xrPos + 1]) - sfpow * qupvt.pow43[l3[1]];
      xfsf += x[0] * x[0] + x[1] * x[1];
    }
    return xfsf;
  }

  ;

  private boolean tri_calc_sfb_noise_x34(final float[] xr,
                                         final float[] xr34, final int xrPos, final float l3_xmin,
                                         final int bw, final int sf, final CalcNoiseCache[] did_it) {
    if (did_it[sf].valid == 0) {
      did_it[sf].valid = 1;
      did_it[sf].value = calc_sfb_noise_x34(xr, xr34, xrPos, bw, sf);
    }
    if (l3_xmin < did_it[sf].value) {
      return true;
    }
    if (sf < 255) {
      final int sf_x = sf + 1;
      if (did_it[sf_x].valid == 0) {
        did_it[sf_x].valid = 1;
        did_it[sf_x].value = calc_sfb_noise_x34(xr, xr34, xrPos, bw,
            sf_x);
      }
      if (l3_xmin < did_it[sf_x].value) {
        return true;
      }
    }
    if (sf > 0) {
      final int sf_x = sf - 1;
      if (did_it[sf_x].valid == 0) {
        did_it[sf_x].valid = 1;
        did_it[sf_x].value = calc_sfb_noise_x34(xr, xr34, xrPos, bw,
            sf_x);
      }
      if (l3_xmin < did_it[sf_x].value) {
        return true;
      }
    }
    return false;
  }

  /**
   * the find_scalefac* routines calculate a quantization step size which
   * would introduce as much noise as is allowed. The larger the step size the
   * more quantization noise we'll get. The scalefactors are there to lower
   * the global step size, allowing limited differences in quantization step
   * sizes per band (shaping the noise).
   */
  private int find_scalefac_x34(final float[] xr, final float[] xr34,
                                final int xrPos, final float l3_xmin, final int bw, final int sf_min) {
    CalcNoiseCache did_it[] = new CalcNoiseCache[256];
    int sf = 128, sf_ok = 255, delsf = 128, seen_good_one = 0, i;
    for (int j = 0; j < did_it.length; j++) {
      did_it[j] = new CalcNoiseCache();
    }
    for (i = 0; i < 8; ++i) {
      delsf >>= 1;
      if (sf <= sf_min) {
        sf += delsf;
      } else {
        final boolean bad = tri_calc_sfb_noise_x34(xr, xr34, xrPos,
            l3_xmin, bw, sf, did_it);
        if (bad) {
          /* distortion. try a smaller scalefactor */
          sf -= delsf;
        } else {
          sf_ok = sf;
          sf += delsf;
          seen_good_one = 1;
        }
      }
    }
    // returning a scalefac without distortion, if possible
    if (seen_good_one > 0) {
      return sf_ok;
    }
    if (sf <= sf_min) {
      return sf_min;
    }
    return sf;
  }

  /**
   * calc_short_block_vbr_sf(), calc_long_block_vbr_sf()
   * <p/>
   * a variation for vbr-mtrh
   *
   * @author Mark Taylor 2000-??-??
   * @author Robert Hegemann 2000-10-25 made functions of it
   */
  private int block_sf(final algo_t that, final float l3_xmin[],
                       final int vbrsf[], final int vbrsfmin[]) {
    float max_xr34;
    final float[] xr = that.cod_info.xr;
    final float[] xr34_orig = that.xr34orig;
    final int[] width = that.cod_info.width;
    final int max_nonzero_coeff = that.cod_info.max_nonzero_coeff;
    int maxsf = 0;
    int sfb = 0;
    int j = 0, i = 0;
    final int psymax = that.cod_info.psymax;

    assert (that.cod_info.max_nonzero_coeff >= 0);

    that.mingain_l = 0;
    that.mingain_s[0] = 0;
    that.mingain_s[1] = 0;
    that.mingain_s[2] = 0;
    while (j <= max_nonzero_coeff) {
      final int w = width[sfb];
      final int m = (max_nonzero_coeff - j + 1);
      int l = w;
      int m1, m2;
      if (l > m) {
        l = m;
      }
      max_xr34 = max_x34(xr34_orig, j, l);

      m1 = findLowestScalefac(max_xr34);
      vbrsfmin[sfb] = m1;
      if (that.mingain_l < m1) {
        that.mingain_l = m1;
      }
      if (that.mingain_s[i] < m1) {
        that.mingain_s[i] = m1;
      }
      if (++i > 2) {
        i = 0;
      }
      if (sfb < psymax) {
        if (belowNoiseFloor(xr, j, l3_xmin[sfb], l) == 0) {
          m2 = find_scalefac_x34(xr, xr34_orig, j, l3_xmin[sfb], l,
              m1);
          if (maxsf < m2) {
            maxsf = m2;
          }
        } else {
          m2 = 255;
          maxsf = 255;
        }
      } else {
        if (maxsf < m1) {
          maxsf = m1;
        }
        m2 = maxsf;
      }
      vbrsf[sfb] = m2;
      ++sfb;
      j += w;
    }
    for (; sfb < L3Side.SFBMAX; ++sfb) {
      vbrsf[sfb] = maxsf;
      vbrsfmin[sfb] = 0;
    }
    return maxsf;
  }

  /**
   * quantize xr34 based on scalefactors
   * <p/>
   * block_xr34
   *
   * @author Mark Taylor 2000-??-??
   * @author Robert Hegemann 2000-10-20 made functions of them
   */
  private final void quantize_x34(final algo_t that) {
    double x[] = new double[4];
    int xr34_orig = 0;
    final GrInfo cod_info = that.cod_info;
    final int ifqstep = (cod_info.scalefac_scale == 0) ? 2 : 4;
    int l3 = 0;
    int j = 0, sfb = 0;
    final int max_nonzero_coeff = cod_info.max_nonzero_coeff;

    assert (cod_info.max_nonzero_coeff >= 0);
    assert (cod_info.max_nonzero_coeff < 576);

    while (j <= max_nonzero_coeff) {
      final int s = (cod_info.scalefac[sfb] + (cod_info.preflag != 0 ? qupvt.pretab[sfb]
          : 0))
          * ifqstep
          + cod_info.subblock_gain[cod_info.window[sfb]]
          * 8;
      final int sfac = (cod_info.global_gain - s);
      final float sfpow34 = qupvt.ipow20[sfac];
      final int w = cod_info.width[sfb];
      final int m = (max_nonzero_coeff - j + 1);
      int l = w;
      int remaining;

      assert ((cod_info.global_gain - s) >= 0);
      assert (cod_info.width[sfb] >= 0);

      if (l > m) {
        l = m;
      }
      j += w;
      ++sfb;
      l >>= 1;
      remaining = (l & 1);

      for (l >>= 1; l > 0; --l) {
        x[0] = sfpow34 * that.xr34orig[xr34_orig + 0];
        x[1] = sfpow34 * that.xr34orig[xr34_orig + 1];
        x[2] = sfpow34 * that.xr34orig[xr34_orig + 2];
        x[3] = sfpow34 * that.xr34orig[xr34_orig + 3];

        k_34_4(x, cod_info.l3_enc, l3);

        l3 += 4;
        xr34_orig += 4;
      }
      if (remaining != 0) {
        x[0] = sfpow34 * that.xr34orig[xr34_orig + 0];
        x[1] = sfpow34 * that.xr34orig[xr34_orig + 1];

        k_34_2(x, cod_info.l3_enc, l3);

        l3 += 2;
        xr34_orig += 2;
      }
    }
  }

  protected void set_subblock_gain(final GrInfo cod_info,
                                   final int mingain_s[], final int sf[]) {
    final int maxrange1 = 15, maxrange2 = 7;
    final int ifqstepShift = (cod_info.scalefac_scale == 0) ? 1 : 2;
    int[] sbg = cod_info.subblock_gain;
    final int psymax = (int) cod_info.psymax;
    int psydiv = 18;
    int sbg0, sbg1, sbg2;
    int sfb;
    int min_sbg = 7;

    if (psydiv > psymax) {
      psydiv = psymax;
    }
    for (int i = 0; i < 3; ++i) {
      int maxsf1 = 0, maxsf2 = 0, minsf = 1000;
			/* see if we should use subblock gain */
      for (sfb = i; sfb < psydiv; sfb += 3) {
				/* part 1 */
        final int v = -sf[sfb];
        if (maxsf1 < v) {
          maxsf1 = v;
        }
        if (minsf > v) {
          minsf = v;
        }
      }
      for (; sfb < L3Side.SFBMAX; sfb += 3) {
				/* part 2 */
        final int v = -sf[sfb];
        if (maxsf2 < v) {
          maxsf2 = v;
        }
        if (minsf > v) {
          minsf = v;
        }
      }

			/*
			 * boost subblock gain as little as possible so we can reach maxsf1
			 * with scalefactors 8*sbg >= maxsf1
			 */
      {
        final int m1 = maxsf1 - (maxrange1 << ifqstepShift);
        final int m2 = maxsf2 - (maxrange2 << ifqstepShift);

        maxsf1 = Math.max(m1, m2);
      }
      if (minsf > 0) {
        sbg[i] = minsf >> 3;
      } else {
        sbg[i] = 0;
      }
      if (maxsf1 > 0) {
        final int m1 = sbg[i];
        final int m2 = (maxsf1 + 7) >> 3;
        sbg[i] = Math.max(m1, m2);
      }
      if (sbg[i] > 0
          && mingain_s[i] > (cod_info.global_gain - sbg[i] * 8)) {
        sbg[i] = (cod_info.global_gain - mingain_s[i]) >> 3;
      }
      if (sbg[i] > 7) {
        sbg[i] = 7;
      }
      if (min_sbg > sbg[i]) {
        min_sbg = sbg[i];
      }
    }
    sbg0 = sbg[0] * 8;
    sbg1 = sbg[1] * 8;
    sbg2 = sbg[2] * 8;
    for (sfb = 0; sfb < L3Side.SFBMAX; sfb += 3) {
      sf[sfb + 0] += sbg0;
      sf[sfb + 1] += sbg1;
      sf[sfb + 2] += sbg2;
    }
    if (min_sbg > 0) {
      for (int i = 0; i < 3; ++i) {
        sbg[i] -= min_sbg;
      }
      cod_info.global_gain -= min_sbg * 8;
    }
  }

  protected void set_scalefacs(final GrInfo cod_info,
                               final int[] vbrsfmin, final int sf[], final int[] max_range) {
    final int ifqstep = (cod_info.scalefac_scale == 0) ? 2 : 4;
    final int ifqstepShift = (cod_info.scalefac_scale == 0) ? 1 : 2;
    final int[] scalefac = cod_info.scalefac;
    final int sfbmax = cod_info.sfbmax;
    final int[] sbg = cod_info.subblock_gain;
    final int[] window = cod_info.window;
    final int preflag = cod_info.preflag;

    if (preflag != 0) {
      for (int sfb = 11; sfb < sfbmax; ++sfb) {
        sf[sfb] += qupvt.pretab[sfb] * ifqstep;
      }
    }
    for (int sfb = 0; sfb < sfbmax; ++sfb) {
      final int gain = cod_info.global_gain - (sbg[window[sfb]] * 8)
          - ((preflag != 0 ? qupvt.pretab[sfb] : 0) * ifqstep);

      if (sf[sfb] < 0) {
        final int m = gain - vbrsfmin[sfb];
				/* ifqstep*scalefac >= -sf[sfb], so round UP */
        scalefac[sfb] = (ifqstep - 1 - sf[sfb]) >> ifqstepShift;

        if (scalefac[sfb] > max_range[sfb]) {
          scalefac[sfb] = max_range[sfb];
        }
        if (scalefac[sfb] > 0 && (scalefac[sfb] << ifqstepShift) > m) {
          scalefac[sfb] = m >> ifqstepShift;
        }
      } else {
        scalefac[sfb] = 0;
      }
    }
    for (int sfb = sfbmax; sfb < L3Side.SFBMAX; ++sfb) {
      scalefac[sfb] = 0; /* sfb21 */
    }
  }

  protected boolean checkScalefactor(final GrInfo cod_info,
                                     final int vbrsfmin[]) {
    final int ifqstep = cod_info.scalefac_scale == 0 ? 2 : 4;
    for (int sfb = 0; sfb < cod_info.psymax; ++sfb) {
      final int s = ((cod_info.scalefac[sfb] + (cod_info.preflag != 0 ? qupvt.pretab[sfb]
          : 0)) * ifqstep)
          + cod_info.subblock_gain[cod_info.window[sfb]] * 8;

      if ((cod_info.global_gain - s) < vbrsfmin[sfb]) {
        /**
         * <CODE>
         * fprintf( stdout, "sf %d\n", sfb );
         * fprintf( stdout, "min %d\n", vbrsfmin[sfb] );
         * fprintf( stdout, "ggain %d\n", cod_info.global_gain );
         * fprintf( stdout, "scalefac %d\n", cod_info.scalefac[sfb] );
         * fprintf( stdout, "pretab %d\n", (cod_info.preflag ? pretab[sfb] : 0) );
         * fprintf( stdout, "scale %d\n", (cod_info.scalefac_scale + 1) );
         * fprintf( stdout, "subgain %d\n", cod_info.subblock_gain[cod_info.window[sfb]] * 8 );
         * fflush( stdout );
         * exit(-1);
         * </CODE>
         */
        return false;
      }
    }
    return true;
  }

  private void bitcount(final algo_t that) {
    boolean rc;

    if (that.gfc.mode_gr == 2) {
      rc = tak.scale_bitcount(that.cod_info);
    } else {
      rc = tak.scale_bitcount_lsf(that.gfc, that.cod_info);
    }
    if (!rc) {
      return;
    }
		/* this should not happen due to the way the scalefactors are selected */
    throw new RuntimeException("INTERNAL ERROR IN VBR NEW CODE (986), please send bug report");
  }

  private int quantizeAndCountBits(final algo_t that) {
    quantize_x34(that);
    that.cod_info.part2_3_length = tak.noquant_count_bits(that.gfc,
        that.cod_info, null);
    return that.cod_info.part2_3_length;
  }

  private int tryGlobalStepsize(final algo_t that, final int sfwork[],
                                final int vbrsfmin[], int delta) {
    final float xrpow_max = that.cod_info.xrpow_max;
    int sftemp[] = new int[L3Side.SFBMAX], nbits;
    int vbrmax = 0;
    for (int i = 0; i < L3Side.SFBMAX; ++i) {
      int gain = sfwork[i] + delta;
      if (gain < vbrsfmin[i]) {
        gain = vbrsfmin[i];
      }
      if (gain > 255) {
        gain = 255;
      }
      if (vbrmax < gain) {
        vbrmax = gain;
      }
      sftemp[i] = gain;
    }
    that.alloc.alloc(that, sftemp, vbrsfmin, vbrmax);
    bitcount(that);
    nbits = quantizeAndCountBits(that);
    that.cod_info.xrpow_max = xrpow_max;
    return nbits;
  }

  private void searchGlobalStepsizeMax(final algo_t that, final int sfwork[],
                                       final int vbrsfmin[], final int target) {
    final GrInfo cod_info = that.cod_info;
    final int gain = cod_info.global_gain;
    int curr = gain;
    int gain_ok = 1024;
    int nbits = QuantizePVT.LARGE_BITS;
    int l = gain, r = 512;

    assert (gain >= 0);
    while (l <= r) {
      curr = (l + r) >> 1;
      nbits = tryGlobalStepsize(that, sfwork, vbrsfmin, curr - gain);
      if (nbits == 0 || (nbits + cod_info.part2_length) < target) {
        r = curr - 1;
        gain_ok = curr;
      } else {
        l = curr + 1;
        if (gain_ok == 1024) {
          gain_ok = curr;
        }
      }
    }
    if (gain_ok != curr) {
      curr = gain_ok;
      nbits = tryGlobalStepsize(that, sfwork, vbrsfmin, curr - gain);
    }
  }

  private int sfDepth(final int sfwork[]) {
    int m = 0;
    for (int j = L3Side.SFBMAX, i = 0; j > 0; --j, ++i) {
      final int di = 255 - sfwork[i];
      if (m < di) {
        m = di;
      }
      assert (sfwork[i] >= 0);
      assert (sfwork[i] <= 255);
    }
    assert (m >= 0);
    assert (m <= 255);
    return m;
  }

  private void cutDistribution(final int sfwork[], final int sf_out[],
                               final int cut) {
    for (int j = L3Side.SFBMAX, i = 0; j > 0; --j, ++i) {
      final int x = sfwork[i];
      sf_out[i] = x < cut ? x : cut;
    }
  }

  private int flattenDistribution(final int sfwork[], final int sf_out[],
                                  final int dm, final int k, final int p) {
    int sfmax = 0;
    if (dm > 0) {
      for (int j = L3Side.SFBMAX, i = 0; j > 0; --j, ++i) {
        final int di = p - sfwork[i];
        int x = sfwork[i] + (k * di) / dm;
        if (x < 0) {
          x = 0;
        } else {
          if (x > 255) {
            x = 255;
          }
        }
        sf_out[i] = x;
        if (sfmax < x) {
          sfmax = x;
        }
      }
    } else {
      for (int j = L3Side.SFBMAX, i = 0; j > 0; --j, ++i) {
        int x = sfwork[i];
        sf_out[i] = x;
        if (sfmax < x) {
          sfmax = x;
        }
      }
    }
    return sfmax;
  }

  private int tryThatOne(final algo_t that, final int sftemp[],
                         final int vbrsfmin[], final int vbrmax) {
    final float xrpow_max = that.cod_info.xrpow_max;
    int nbits = QuantizePVT.LARGE_BITS;
    that.alloc.alloc(that, sftemp, vbrsfmin, vbrmax);
    bitcount(that);
    nbits = quantizeAndCountBits(that);
    nbits += that.cod_info.part2_length;
    that.cod_info.xrpow_max = xrpow_max;
    return nbits;
  }

  private void outOfBitsStrategy(final algo_t that, final int sfwork[],
                                 final int vbrsfmin[], final int target) {
    int wrk[] = new int[L3Side.SFBMAX];
    final int dm = sfDepth(sfwork);
    final int p = that.cod_info.global_gain;

		/* PART 1 */
    {
      int bi = dm / 2;
      int bi_ok = -1;
      int bu = 0;
      int bo = dm;
      for (; ; ) {
        final int sfmax = flattenDistribution(sfwork, wrk, dm, bi, p);
        int nbits = tryThatOne(that, wrk, vbrsfmin, sfmax);
        if (nbits <= target) {
          bi_ok = bi;
          bo = bi - 1;
        } else {
          bu = bi + 1;
        }
        if (bu <= bo) {
          bi = (bu + bo) / 2;
        } else {
          break;
        }
      }
      if (bi_ok >= 0) {
        if (bi != bi_ok) {
          final int sfmax = flattenDistribution(sfwork, wrk, dm,
              bi_ok, p);
          tryThatOne(that, wrk, vbrsfmin, sfmax);
        }
        return;
      }
    }

		/* PART 2: */
    {
      int bi = (255 + p) / 2;
      int bi_ok = -1;
      int bu = p;
      int bo = 255;
      for (; ; ) {
        final int sfmax = flattenDistribution(sfwork, wrk, dm, dm, bi);
        int nbits = tryThatOne(that, wrk, vbrsfmin, sfmax);
        if (nbits <= target) {
          bi_ok = bi;
          bo = bi - 1;
        } else {
          bu = bi + 1;
        }
        if (bu <= bo) {
          bi = (bu + bo) / 2;
        } else {
          break;
        }
      }
      if (bi_ok >= 0) {
        if (bi != bi_ok) {
          final int sfmax = flattenDistribution(sfwork, wrk, dm, dm,
              bi_ok);
          tryThatOne(that, wrk, vbrsfmin, sfmax);
        }
        return;
      }
    }

		/* fall back to old code, likely to be never called */
    searchGlobalStepsizeMax(that, wrk, vbrsfmin, target);
  }

  private int reduce_bit_usage(final LameInternalFlags gfc, final int gr,
                               final int ch) {
    final GrInfo cod_info = gfc.l3_side.tt[gr][ch];
    // try some better scalefac storage
    tak.best_scalefac_store(gfc, gr, ch, gfc.l3_side);

    // best huffman_divide may save some bits too
    if (gfc.use_best_huffman == 1)
      tak.best_huffman_divide(gfc, cod_info);
    return cod_info.part2_3_length + cod_info.part2_length;
  }

  public int VBR_encode_frame(final LameInternalFlags gfc,
                              final float xr34orig[][][], final float l3_xmin[][][],
                              final int max_bits[][]) {
    int sfwork_[][][] = new int[2][2][L3Side.SFBMAX];
    int vbrsfmin_[][][] = new int[2][2][L3Side.SFBMAX];
    algo_t that_[][] = new algo_t[2][2];
    final int ngr = gfc.mode_gr;
    final int nch = gfc.channels_out;
    int max_nbits_ch[][] = new int[2][2];
    int max_nbits_gr[] = new int[2];
    int max_nbits_fr = 0;
    int use_nbits_ch[][] = new int[2][2];
    int use_nbits_gr[] = new int[2];
    int use_nbits_fr = 0;

		/*
		 * set up some encoding parameters
		 */
    for (int gr = 0; gr < ngr; ++gr) {
      max_nbits_gr[gr] = 0;
      for (int ch = 0; ch < nch; ++ch) {
        max_nbits_ch[gr][ch] = max_bits[gr][ch];
        use_nbits_ch[gr][ch] = 0;
        max_nbits_gr[gr] += max_bits[gr][ch];
        max_nbits_fr += max_bits[gr][ch];
        that_[gr][ch] = new algo_t();
        that_[gr][ch].gfc = gfc;
        that_[gr][ch].cod_info = gfc.l3_side.tt[gr][ch];
        that_[gr][ch].xr34orig = xr34orig[gr][ch];
        if (that_[gr][ch].cod_info.block_type == Encoder.SHORT_TYPE) {
          that_[gr][ch].alloc = new ShortBlockConstrain(this);
        } else {
          that_[gr][ch].alloc = new LongBlockConstrain(this);
        }
      } /* for ch */
    }

		/*
		 * searches scalefactors
		 */
    for (int gr = 0; gr < ngr; ++gr) {
      for (int ch = 0; ch < nch; ++ch) {
        if (max_bits[gr][ch] > 0) {
          algo_t that = that_[gr][ch];
          int[] sfwork = sfwork_[gr][ch];
          int[] vbrsfmin = vbrsfmin_[gr][ch];
          int vbrmax;

          vbrmax = block_sf(that, l3_xmin[gr][ch], sfwork, vbrsfmin);
          that.alloc.alloc(that, sfwork, vbrsfmin, vbrmax);
          bitcount(that);
        } else {
					/*
					 * xr contains no energy l3_enc, our encoding data, will be
					 * quantized to zero continue with next channel
					 */
        }
      } /* for ch */
    }

		/*
		 * encode 'as is'
		 */
    use_nbits_fr = 0;
    for (int gr = 0; gr < ngr; ++gr) {
      use_nbits_gr[gr] = 0;
      for (int ch = 0; ch < nch; ++ch) {
        algo_t that = that_[gr][ch];
        if (max_bits[gr][ch] > 0) {
          final int max_nonzero_coeff = that.cod_info.max_nonzero_coeff;

          assert (max_nonzero_coeff < 576);
          Arrays.fill(that.cod_info.l3_enc, max_nonzero_coeff, 576, 0);

          quantizeAndCountBits(that);
        } else {
					/*
					 * xr contains no energy l3_enc, our encoding data, will be
					 * quantized to zero continue with next channel
					 */
        }
        use_nbits_ch[gr][ch] = reduce_bit_usage(gfc, gr, ch);
        use_nbits_gr[gr] += use_nbits_ch[gr][ch];
      } /* for ch */
      use_nbits_fr += use_nbits_gr[gr];
    }

		/*
		 * check bit constrains
		 */
    if (use_nbits_fr <= max_nbits_fr) {
      boolean ok = true;
      for (int gr = 0; gr < ngr; ++gr) {
        if (use_nbits_gr[gr] > LameInternalFlags.MAX_BITS_PER_GRANULE) {
					/*
					 * violates the rule that every granule has to use no more
					 * bits than MAX_BITS_PER_GRANULE
					 */
          ok = false;
        }
        for (int ch = 0; ch < nch; ++ch) {
          if (use_nbits_ch[gr][ch] > LameInternalFlags.MAX_BITS_PER_CHANNEL) {
						/*
						 * violates the rule that every gr_ch has to use no more
						 * bits than MAX_BITS_PER_CHANNEL
						 *
						 * This isn't explicitly stated in the ISO docs, but the
						 * part2_3_length field has only 12 bits, that makes it
						 * up to a maximum size of 4095 bits!!!
						 */
            ok = false;
          }
        }
      }
      if (ok) {
        return use_nbits_fr;
      }
    }

		/*
		 * OK, we are in trouble and have to define how many bits are to be used
		 * for each granule
		 */
    {
      boolean ok = true;
      int sum_fr = 0;

      for (int gr = 0; gr < ngr; ++gr) {
        max_nbits_gr[gr] = 0;
        for (int ch = 0; ch < nch; ++ch) {
          if (use_nbits_ch[gr][ch] > LameInternalFlags.MAX_BITS_PER_CHANNEL) {
            max_nbits_ch[gr][ch] = LameInternalFlags.MAX_BITS_PER_CHANNEL;
          } else {
            max_nbits_ch[gr][ch] = use_nbits_ch[gr][ch];
          }
          max_nbits_gr[gr] += max_nbits_ch[gr][ch];
        }
        if (max_nbits_gr[gr] > LameInternalFlags.MAX_BITS_PER_GRANULE) {
          float f[] = new float[2], s = 0;
          for (int ch = 0; ch < nch; ++ch) {
            if (max_nbits_ch[gr][ch] > 0) {
              f[ch] = (float) Math.sqrt(Math
                  .sqrt(max_nbits_ch[gr][ch]));
              s += f[ch];
            } else {
              f[ch] = 0;
            }
          }
          for (int ch = 0; ch < nch; ++ch) {
            if (s > 0) {
              max_nbits_ch[gr][ch] = (int) (LameInternalFlags.MAX_BITS_PER_GRANULE
                  * f[ch] / s);
            } else {
              max_nbits_ch[gr][ch] = 0;
            }
          }
          if (nch > 1) {
            if (max_nbits_ch[gr][0] > use_nbits_ch[gr][0] + 32) {
              max_nbits_ch[gr][1] += max_nbits_ch[gr][0];
              max_nbits_ch[gr][1] -= use_nbits_ch[gr][0] + 32;
              max_nbits_ch[gr][0] = use_nbits_ch[gr][0] + 32;
            }
            if (max_nbits_ch[gr][1] > use_nbits_ch[gr][1] + 32) {
              max_nbits_ch[gr][0] += max_nbits_ch[gr][1];
              max_nbits_ch[gr][0] -= use_nbits_ch[gr][1] + 32;
              max_nbits_ch[gr][1] = use_nbits_ch[gr][1] + 32;
            }
            if (max_nbits_ch[gr][0] > LameInternalFlags.MAX_BITS_PER_CHANNEL) {
              max_nbits_ch[gr][0] = LameInternalFlags.MAX_BITS_PER_CHANNEL;
            }
            if (max_nbits_ch[gr][1] > LameInternalFlags.MAX_BITS_PER_CHANNEL) {
              max_nbits_ch[gr][1] = LameInternalFlags.MAX_BITS_PER_CHANNEL;
            }
          }
          max_nbits_gr[gr] = 0;
          for (int ch = 0; ch < nch; ++ch) {
            max_nbits_gr[gr] += max_nbits_ch[gr][ch];
          }
        }
        sum_fr += max_nbits_gr[gr];
      }
      if (sum_fr > max_nbits_fr) {
        {
          float f[] = new float[2], s = 0;
          for (int gr = 0; gr < ngr; ++gr) {
            if (max_nbits_gr[gr] > 0) {
              f[gr] = (float) Math.sqrt(max_nbits_gr[gr]);
              s += f[gr];
            } else {
              f[gr] = 0;
            }
          }
          for (int gr = 0; gr < ngr; ++gr) {
            if (s > 0) {
              max_nbits_gr[gr] = (int) (max_nbits_fr * f[gr] / s);
            } else {
              max_nbits_gr[gr] = 0;
            }
          }
        }
        if (ngr > 1) {
          if (max_nbits_gr[0] > use_nbits_gr[0] + 125) {
            max_nbits_gr[1] += max_nbits_gr[0];
            max_nbits_gr[1] -= use_nbits_gr[0] + 125;
            max_nbits_gr[0] = use_nbits_gr[0] + 125;
          }
          if (max_nbits_gr[1] > use_nbits_gr[1] + 125) {
            max_nbits_gr[0] += max_nbits_gr[1];
            max_nbits_gr[0] -= use_nbits_gr[1] + 125;
            max_nbits_gr[1] = use_nbits_gr[1] + 125;
          }
          for (int gr = 0; gr < ngr; ++gr) {
            if (max_nbits_gr[gr] > LameInternalFlags.MAX_BITS_PER_GRANULE) {
              max_nbits_gr[gr] = LameInternalFlags.MAX_BITS_PER_GRANULE;
            }
          }
        }
        for (int gr = 0; gr < ngr; ++gr) {
          float f[] = new float[2], s = 0;
          for (int ch = 0; ch < nch; ++ch) {
            if (max_nbits_ch[gr][ch] > 0) {
              f[ch] = (float) Math.sqrt(max_nbits_ch[gr][ch]);
              s += f[ch];
            } else {
              f[ch] = 0;
            }
          }
          for (int ch = 0; ch < nch; ++ch) {
            if (s > 0) {
              max_nbits_ch[gr][ch] = (int) (max_nbits_gr[gr]
                  * f[ch] / s);
            } else {
              max_nbits_ch[gr][ch] = 0;
            }
          }
          if (nch > 1) {
            if (max_nbits_ch[gr][0] > use_nbits_ch[gr][0] + 32) {
              max_nbits_ch[gr][1] += max_nbits_ch[gr][0];
              max_nbits_ch[gr][1] -= use_nbits_ch[gr][0] + 32;
              max_nbits_ch[gr][0] = use_nbits_ch[gr][0] + 32;
            }
            if (max_nbits_ch[gr][1] > use_nbits_ch[gr][1] + 32) {
              max_nbits_ch[gr][0] += max_nbits_ch[gr][1];
              max_nbits_ch[gr][0] -= use_nbits_ch[gr][1] + 32;
              max_nbits_ch[gr][1] = use_nbits_ch[gr][1] + 32;
            }
            for (int ch = 0; ch < nch; ++ch) {
              if (max_nbits_ch[gr][ch] > LameInternalFlags.MAX_BITS_PER_CHANNEL) {
                max_nbits_ch[gr][ch] = LameInternalFlags.MAX_BITS_PER_CHANNEL;
              }
            }
          }
        }
      }
			/* sanity check */
      sum_fr = 0;
      for (int gr = 0; gr < ngr; ++gr) {
        int sum_gr = 0;
        for (int ch = 0; ch < nch; ++ch) {
          sum_gr += max_nbits_ch[gr][ch];
          if (max_nbits_ch[gr][ch] > LameInternalFlags.MAX_BITS_PER_CHANNEL) {
            ok = false;
          }
        }
        sum_fr += sum_gr;
        if (sum_gr > LameInternalFlags.MAX_BITS_PER_GRANULE) {
          ok = false;
        }
      }
      if (sum_fr > max_nbits_fr) {
        ok = false;
      }
      if (!ok) {
				/*
				 * we must have done something wrong, fallback to 'on_pe' based
				 * constrain
				 */
        for (int gr = 0; gr < ngr; ++gr) {
          for (int ch = 0; ch < nch; ++ch) {
            max_nbits_ch[gr][ch] = max_bits[gr][ch];
          }
        }
      }
    }

		/*
		 * we already called the 'best_scalefac_store' function, so we need to
		 * reset some variables before we can do it again.
		 */
    for (int ch = 0; ch < nch; ++ch) {
      gfc.l3_side.scfsi[ch][0] = 0;
      gfc.l3_side.scfsi[ch][1] = 0;
      gfc.l3_side.scfsi[ch][2] = 0;
      gfc.l3_side.scfsi[ch][3] = 0;
    }
    for (int gr = 0; gr < ngr; ++gr) {
      for (int ch = 0; ch < nch; ++ch) {
        gfc.l3_side.tt[gr][ch].scalefac_compress = 0;
      }
    }

		/*
		 * alter our encoded data, until it fits into the target bitrate
		 */
    use_nbits_fr = 0;
    for (int gr = 0; gr < ngr; ++gr) {
      use_nbits_gr[gr] = 0;
      for (int ch = 0; ch < nch; ++ch) {
        algo_t that = that_[gr][ch];
        use_nbits_ch[gr][ch] = 0;
        if (max_bits[gr][ch] > 0) {
          int[] sfwork = sfwork_[gr][ch];
          int[] vbrsfmin = vbrsfmin_[gr][ch];
          cutDistribution(sfwork, sfwork, that.cod_info.global_gain);
          outOfBitsStrategy(that, sfwork, vbrsfmin,
              max_nbits_ch[gr][ch]);
        }
        use_nbits_ch[gr][ch] = reduce_bit_usage(gfc, gr, ch);
        assert (use_nbits_ch[gr][ch] <= max_nbits_ch[gr][ch]);
        use_nbits_gr[gr] += use_nbits_ch[gr][ch];
      } /* for ch */
      use_nbits_fr += use_nbits_gr[gr];
    }

		/*
		 * check bit constrains, but it should always be ok, if there are no
		 * bugs ;-)
		 */
    if (use_nbits_fr <= max_nbits_fr) {
      return use_nbits_fr;
    }

    throw new RuntimeException(String.format(
        "INTERNAL ERROR IN VBR NEW CODE (1313), please send bug report\n"
            + "maxbits=%d usedbits=%d\n", max_nbits_fr,
        use_nbits_fr));
  }

  interface alloc_sf_f {
    void alloc(final algo_t al, final int[] x, final int[] y, final int z);
  }

  protected static class algo_t {
    alloc_sf_f alloc;
    float[] xr34orig;
    LameInternalFlags gfc;
    GrInfo cod_info;
    int mingain_l;
    int mingain_s[] = new int[3];
  }

  protected static class CalcNoiseCache {
    int valid;
    float value;
  }

}
